In digital facsimile systems a document is scanned line by line to generate digitized data. Each bit of information, either a "1" or "0", corresponds to a small area on the document. The "color" of the area, i.e., whether the area is white or black, determines whether the associated binary signal is a "0" or a "1", respectively.
These lines of picture data are normally comprised of units of alternating color having various run lengths. For example, a line of picture data might have a white color unit of ten picture elements which represents a blank space in the document. This first color unit has a run length of ten. The next color unit is naturally black and may contain five picture elements for a run length of five. This color unit may represent part of a character on the document. Thus each line of picture data has an alternating sequence of white and black color units, each having a particular run length.
Since the straightforward transmission of this data may involve a large amount of digital information and may therefore consume much time, recent advances in the facsimile field have been made in the encoding of the information so that the amount of data which is required for transmission is compressed. These advances include the sequential coding of run lengths, color unit by color unit on a line, and line by line until the entire document is coded. This is called one-dimensional or run length coding. Another approach is the sequential coding of the positions of the first picture element of each color unit in a line to be coded (the coding line) with respect to the positions of the first picture element of color units in a line which has already been coded (the reference line). This coding procedure, which is repeated line by line, is called two-dimensional coding. For an explanation of digital coding standards, see "International Digital Facsimile Coding Standards," by R. Hunter and A. H. Robinson in the Preceeding of the IEEE, Volume 68, No. 7, July 1980, pages 854-867.
The present applicants have also developed a method of an a device for coding facsimile data in accordance with the above coding procedure. A disclosure of this method and the device is made in a patent application, U.S. Ser. No. 524,919, entitled METHOD AND DEVICE FOR TWO-DIMENSIONAL FACSIMILE CODING, filed of even date by the present applications. A related invention is disclosed in another patent application U.S. Ser. No. 524,917, entitled A FACSIMILE DEVICE FOR RUN LENGTH CODING, also filed of even date by the present application.
The encoded data is transmitted to a distant location, received, and reformed to obtain a copy of the original document. The facsimile receiver has a decoding unit for decoding the compressed data into signals indicating the run lengths of successive color units. These run length signals are fed into a picture element generating unit which transforms the run length signals to picture element signals to reform the original document color unit by color unit and line by line. In an ideal transmission-reception there should be a one-to-one correspondence between the picture elements at the transmission end and the picture elements at the reception end.
The basic structure of a facsimile receiver is shown in FIG. 1. The timing and the operation of a decoder unit 310 and a picture element generator 313 is controlled by a control logic unit 315 which communicates with the decoder by a control path 316 and to the picture element generator along a data path 317. The decoder 310 receives the encoded data on a data path 311. This data is in the form of a sequence of "1"'s and "0"'s which correspond to lines of a document which has been scanned by the digital facsimile transmitter. This encoded data is represented by an arbitrary sequence in the uppermost line of data in FIG. 1.
The encoded data signals are accepted by the decoder 310 and transformed into run length data which indicate the color and run length of sequential color units. FIG. 1 shows that first line of data corresponds to a sequence of color units starting on the left with a white color unit of two picture elements, a black unit with two picture elements, a third white color unit with three elements and so forth.
The run length data enters the picture element generator 313 on the data path 312. The generator 313 then forms the picture element data from the run length data. Corresponding to the initial white color unit of two picture elements, the picture element data generates with two ZERO signals. Corresponding to the black color unit of two pictures elements, the picture element generator 313 forms two ONE signals after the picture elements for the first color unit. Then the picture element generator 313 generates three ZEROS corresponding to the third white color unit and so on.
One such novel picture element generator suitable for high speed operation and integration using VLSI (Very Large Scale Integration) technology is disclosed in a patent application, U.S. Ser. No. 524,957, filed of even date by the present applicants, entitled PICTURE ELEMENT GENERATOR FOR FACSIMILE RECEIVER.
The picture element data is then sent to a printer or other marking device and, with a one for one relationship, sets the picture element data signals down on a copy. The bottommost line illustrates the physical representation of the picture element data signals. By line by line decoding, picture element generation, and printing, a copy of the original document is formed and the facsimile operation performed.
The present invention is directed toward a high speed decoding unit. In the prior art the coded or compressed data is stored in a memory and decoded or expanded by the decoding logic. This data after being loaded in parallel into the memory is processed by the decoding logic one bit at a time to perform the expansion of the data into the original picture element data. This process of data one bit at a time is an obstacle to high speed operation. As can be seen in U.S. Pat. No. 4,258,392, issued to Y. Yamazaki et al. on Mar. 24, 1981, the decoding process requires the determination of a.sub.0, a.sub.1, a.sub.2, b.sub.1 and b.sub.2 picture elements and the calculation of terms such as a.sub.0 -b.sub.1, a.sub.0 -b.sub.2, b.sub.2 -a.sub.2, b.sub.1 -a.sub.1, a.sub.0 -a.sub.1 and a.sub.1 -a.sub.2. The determination and monitoring of the a.sub.0 picture element and the control of the load address of the reference line memory require extremely complicated logic. Furthermore, the address control is complicated and the decoding procedure is slow by the bit by bit processing required.
The present invention avoids many of these problems to achieve a high speed decoding unit suitable for VLSI integration.